/**
 * 153. Find Minimum in Rotated Sorted Array
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
 */
class FindMinimumInRotatedSortedArray {
    /**
     * 方法：二分查找
     * 在旋转排序数组中查找最小值。通过比较中间元素与最后一个元素的大小关系来判断最小值在哪一侧。
     * 如果中间元素小于最后一个元素，说明最小值在左半部分（包括中间元素）；
     * 否则最小值在右半部
     * Args:
     *     nums: List[int], 旋转排序
     * Returns:
     *     int: 数组中的最
     * Time: O(logn)，其中n是数组的长度，每次将搜索范围缩小
     * Space: O(1)，只使用常数额外空间
     */
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = -1;
        int right = n - 1; // 开区间 (-1, n-1)
        while (left + 1 < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] < nums[n-1]){
                right = mid;
            }else{
                left = mid;
            }
        }
        return nums[right];
    }
}